using System;
using System.Collections.Generic;
using System.Linq;

namespace Test.ConsoleProgram.Algorithm.Interview
{
    [TestDescription("面试题 17.13. 恢复空格")]
    public class No00170013_Respace : AbsBaseTestItem
    {
        public override void OnTest()
        {
            Assert.TestExe(Respace,
                new string[] { "looked", "just", "like", "her", "brother" },
                "jesslookedjustliketimherbrother", 7);
            Assert.TestExe(Respace,
                new string[] { "bt", "vbtbvtvvbbvtbvvbbbvbtbbv", "bvvbbbvvvbvttbtbvtvtvvbttbbbtvvvb", "btttbvbbbtbbtbvvttbvbvtvbtbbttb", "bt", "vvbvbvbvtbvbvvvvtv", "tbvvvtttvtbvbtttvvbtvvvvtvvbvvtvvbbvbbbvb", "v", "bvb", "vvtbvtvbttbttvvbvttbt", "btbtbtttvbbtbttbtvvttbvtbtvtbvvtbbbb", "bttbvbbttvvbtvvvvb", "bvvbvbvttbvtbvvtbttvvvvtvbtvbttbbvvtvtvv", "vbtttt", "btbvbbbvbtvtbvvv", "b", "tbtbtv", "vbvbbvvbvbbvvb", "vbvvtvbvbvbttvbvbtvbtbtvtbvbbtb", "bvvbvvttttttbtvvvttvbvtvvbvtbtvtbvttvvtbt", "bvtbttv", "bbbt", "vtt", "ttvv", "b", "vbb", "vtvvbtttvtbbvvbbtbb", "vvv", "vvvvbbbtbbbvbbbb", "ttvvbtvv", "v", "btvbbvtbbvbvtvttvvbbbtbvvvtbtb", "vv", "btbttbtbbvbvvbvttbttvtbbtbvtttvbbtbbtvtvvvvbbttvtvvbbbv", "ttvbbbbttbtbtb", "tvvbvbvvb", "vv", "ttbttvtvbtbbbbv", "bvvvtbbvvvbtvbvtvtvvvvbb", "vtbvvbvvvvvttvbbttbbvtvt", "tbvbbt", "b", "v", "tvbbtvvtvvtbtbttvvvb", "tbttbttbbbtbtvtvtvtbbbvvtbbbvbbvvvbbttvvt", "bbvttvtvvtbvbbttvbbtbvvttbvbvbtbvvvbbbvbvbvbtvbtvvvtvvtbttbttbbvbbbttvvvbvvtb", "vttvvbvv", "tbttbvvttvbtvvtbbvvv", "bvbbbbbbbb", "vtbvvtbbvtt", "bvttbvvbvb", "tvttttbbvvvbbtttvvv" },
                "btbvtttttbvttbvvbbtvvbvbvvbtbtbtvbtttbvbbbtbbtbvvttbvbvtvbtbbttbvvbvbtttbvttbvvbbvvv", 5);
        }

        public int Respace(string[] dictionary, string sentence)
        {
            const long P = int.MaxValue;
            const long BASE = 41;

            long getHash(string s)
            {
                long hashValue = 0;
                for (int i = s.Length - 1; i >= 0; --i)
                {
                    hashValue = (hashValue * BASE + s[i] - 'a' + 1) % P;
                }
                return hashValue;
            };
            HashSet<long> hashValues = new HashSet<long>();
            foreach (var word in dictionary)
            {
                hashValues.Add(getHash(word));
            }

            int[] f = new int[sentence.Length + 1];
            Array.Fill(f, sentence.Length);

            f[0] = 0;
            for (int i = 1; i <= sentence.Length; ++i)
            {
                f[i] = f[i - 1] + 1;
                long hashValue = 0;
                for (int j = i; j >= 1; --j)
                {
                    int t = sentence[j - 1] - 'a' + 1;
                    hashValue = (hashValue * BASE + t) % P;
                    if (hashValues.Contains(hashValue))
                    {
                        f[i] = Math.Min(f[i], f[j - 1]);
                    }
                }
            }
            return f[sentence.Length];
        }

        /// <summary>
        /// 自己写的
        /// </summary>
        public int Respace_self(string[] dictionary, string sentence)
        {
            dictionary = dictionary.OrderByDescending(b => b.Length).ToArray();
            for (int i = 0; i < dictionary.Length; i++)
            {
                sentence = sentence.Replace(dictionary[i], "");
            }
            return sentence.Length;
        }
    }
}
